

import random
import math
import libnum
import time
from Crypto.Util.number import bytes_to_long, long_to_bytes

# 设置模数
def GF(a):
    global p
    p = a


# 乘法取模
def g(a, b):
    global p
    return pow(a, b, p)


def AMM(x, e, p):
    GF(p)
    y = random.randint(1, p - 1)
    while g(y, (p - 1) // e) == 1:
        y = random.randint(1, p - 1)
        print(y)
    # p-1 = e^t*s
    t = 1
    s = 0
    while p % e == 0:
        t += 1
        print(t)
    s = p // (e ** t)
    # s|ralpha-1
    k = 1
    while ((s * k + 1) % e != 0):
        k += 1
    alpha = (s * k + 1) // e
    # 计算a = y^s b = x^s h =1
    # h为e次非剩余部分的积
    a = g(y, (e ** (t - 1)) * s)
    b = g(x, e * alpha - 1)
    c = g(y, s)
    h = 1
    #
    for i in range(1, t - 1):
        d = g(b, e ** (t - 1 - i))
        if d == 1:
            j = 0
        else:
            j = -math.log(d, a)
        b = b * (g(g(c, e), j))
        h = h * g(c, j)
        c = g(c, e)
    # return (g(x, alpha * h)) % p
    root = (g(x, alpha * h)) % p
    roots = set()
    for i in range(e):
        mp2 = root * g(a, i) % p
        # assert(g(mp2, e) == x)
        roots.add(mp2)
    return roots


def check(m):
    if 'flag' in m:
        print(m)
        return True
    else:
        return False

p_= 16615016303456825535806014786811703646376283838640582658113197741213160887351659102120033042679522579691397997102286820032792313366871619145403032684041787668347601125532586216046228787453845648023077839196977988213731572919250810840612646401698521498651188771428303123313530755472299512603048008214095927558621438661082551977154376948293788128403944483254777513764632029157396308445573181589302443973257368798327089561698166080366079136099119484591646534669061663239888903906935958816175600990533027759485952579578063690519585199031597305368978320240607913046462003381934703254895624291202517662906633357935711579169
q_= 20904283217897394580730425738986491074083548599351740840060580231282333197507108184915758658333738669264694789544907976001324742490439178626906581602577153590637615480094594800418999192797801998346244967691995754394613744700689262367970208709505439918311297773972581704402149917219902151008300165384797340849031513219424802706882764102705145804079810688425734249840698043434449864062294754481234740844886658856752044387635402731726810296360529359440571939973678297702076522175970265065650810347773593664294528115405016011328646208196470269505270605763312499001494311808608713762496359715131656428870907622580996540369
c= 792744140679150755507670759628058162324026848159602179964762007590352658808025336708073335633277432422471808722412457662102396270439262283381441624007812926869911510570139226203249198728635686137115206386688496767869761710473244428364705491431257936491072038744014492016364107371322221605272924984185461774061978730541042231296873215451163992744290220666919742609268404811341989258551444653370633707189588582219900283717129458611142394184003058807205308995229039952064162406699929570132014432042138579048496300777873469707229727943494440495926293584415886054281914907662860874879157001800894561498017020142260119951177378751222476221279642515484600895158882475412362264551209755800967943745834255272325771797462246735121607187333973627729441699274640020070294478028338543269738794078331377051968498537304976626894120370645655984454501142485826438436536110364972197312722670582824109388077213809953785272791342291255722374999
n= 2603642818090344204577524643748090948355993170671526468949940986678880107750829818616762234625777092213955514820213981198085970140410427096235916709756603180873321153322737196983421652942053109288711456179091729474679181269413086129651450513748721520939940984810044136480660788881937467176873823274484889589819593175983648130069079842750913995051408911844223662963458356039035404354256924779395800188336268274784442400217106540289131191241620478795546674685141471522432974658679475595284858185058916865190473025897853393557540626893089345267023029608460771767803187486331466955362507314125764379251189271787996932583854040162027432427944522839338865886076503050476901319553569636721895470682551018354303567671655106829289987428283114071129834177114056193267370375851557031229710697128637600606293135751598860617238879990951560816757550601364793767151298046931069830795550777307905030335126755312030398925638782706705223661277
p=libnum.gcd(p_,n)
e=114


mps = AMM(c, e, p)
# print(mps)
for mpp in mps:
    solution = str(long_to_bytes(mpp))
    if check(solution):
        print(solution)